package main

import "fmt"

/*
给定一个N*N的矩阵，只有0和1两个值，
求边框全是1的最大正方形的边长长度
*/
func setQueryMap(matrix [][]int, horizontal [][]int, vertical [][]int) {
	for i := 0; i < len(matrix); i++ {
		for j := len(matrix[0]) - 1; j >= 0; j-- {
			if matrix[i][j] == 1 {
				if j+1 <= len(matrix[0]) - 1 && matrix[i][j+1] == 1 {
					horizontal[i][j] = horizontal[i][j+1] + 1
				} else {
					horizontal[i][j] = 1
				}
			}
		}
	}
	for i := len(matrix) - 1; i >= 0; i-- {
		for j := 0; j < len(matrix[0]); j++ {
			if matrix[i][j] == 1 {
				if i+1 <= len(matrix) - 1 && matrix[i+1][j] == 1 {
					vertical[i][j] = vertical[i+1][j] + 1
				} else {
					vertical[i][j] = 1
				}
			}
		}
	}
}

func isMatrix(matrix [][]int, horizontal [][]int, vertical [][]int, x int, y int, length int) bool {
	if horizontal[y][x] >= length && vertical[y][x] >= length {
		if horizontal[y+length-1][x] >= length && vertical[y][x+length-1] >= length {
			return true
		}
	}
	return false
}

func FindMax(matrix [][]int) int {
	n := len(matrix)
	var horizontal [][]int
	var vertical [][]int
	for i := 0; i < n; i++ {
		horizontal = append(horizontal, make([]int, n))
		vertical = append(vertical, make([]int, n))
	}
	setQueryMap(matrix, horizontal, vertical)
	fmt.Println(horizontal)
	fmt.Println(vertical)

	var max int
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			for length := 1; length < n - i && length < n - j; length++ {
				if isMatrix(matrix, horizontal, vertical, i, j, length) {
					max = Max(max, length)
				}
			}
		}
	}

	return max
}

func main() {
	var m [][]int
	m = [][]int{{0,0,0,0,0,1,1,1,1,0},
				{0,0,0,0,0,1,0,0,1,0},
				{0,0,0,0,0,1,0,0,1,0},
				{0,0,0,0,0,1,1,1,1,0},
				{0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,1,1,1,0,0},
				{0,0,0,0,0,1,1,1,0,0},
				{0,0,0,0,0,1,1,1,0,0},
				{0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0}}
	res := FindMax(m)
	fmt.Println(res)
}

func Max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}